package tree;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.sql.Connection;
import java.util.Stack;

/**
 * 2-3 Tree for indexing document.
 * @author channisa
 *
 */
public class Tree implements Serializable{
	/**
	 * root of tree
	 */
	private Node root;
	
	/**
	 * to trace parent from root to the node that will be search
	 * finding pattern
	 */
	private Stack<Node> stack;
	
	/**
	 * to count value that will be inserted
	 */
	private int jumVal;
	
	
	/**
	 * constructor
	 * @param root
	 */
	public Tree(Node root) {
		this.root = root;
		this.jumVal=1;
	}
	
	/**
	 * get root of the tree
	 * @return root of the tree
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 * set root of the tree
	 * @param node root
	 */
	public void setRoot(Node root) {
		this.root = root;
	}

	/**
	 * get the value that has been inserted to the tree
	 * @return count of value
	 */
	public int getJumVal() {
		return jumVal;
	}
	
	/**
	 * finding x
	 * @param x value that will be found
	 * @return Node, weather its consist x or not. If not leaf node chose -> the x must be consist in the node.
	 */
	public Node trace(int x){
		stack = new Stack<Node>();
		Node current=this.root;
		while (!current.isLeaf()&&current.getValue_left()!=x&&current.getValue_right()!=x) {
			stack.push(current);
			if(current.getValue_right()!=0){
				if(x<current.getValue_left()){
					current=current.getNode_left();
				}else if (x>current.getValue_right()){
					current=current.getNode_right();
				} else {
					current=current.getNode_middle();
				}
			} else {
				if(x<current.getValue_left()){
					current=current.getNode_left();
				} else {
					current=current.getNode_middle();
				}
			}
			
		}
		return current;
	}
	
	/**
	 * finding x value in the tree
	 * @param x value that will be searched
	 * @return NULL if fail to find subject. If success return Node contain x.
	 */
	public Node search(int x){
		Node hasil = trace(x);
		if(hasil.getValue_left()==x||hasil.getValue_right()==x){
//			System.out.println(x+" ketemu.");
			return hasil;
		} else {
//			System.out.println(x+" tidak ketemu.");
			return null;
		}
	}
	
	public boolean isExist (int y){
		Node hasil = trace(y);
		if(hasil.getValue_left()==y||hasil.getValue_right()==y){
//			System.out.println(x+" ketemu.");
			return true;
		} else {
//			System.out.println(x+" tidak ketemu.");
			return false;
		}
	}
	
	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the smallest value will be returned
	 * @param x value that will be inserted and compared to the values in the node
	 * @param y node that will be compared with the new value to find smallest value
	 * @return smallest value
	 */
	public int findSmallValue(int x, Node y){
		int value=0;
		if(x<y.getValue_left()){
			value=x;
		} else {
			value=y.getValue_left();
		}
		return value;
	}
	
	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the middle value will be returned
	 * @param x value that will be inserted and compared to the values in the node
	 * @param y node that will be compared with the new value to find middle value
	 * @return middle value
	 */
	public int findMiddleValue(int x, Node y){
		int value=0;
		if(x<y.getValue_left()){
			value=y.getValue_left();
		} else if (x<y.getValue_right()){
			value=x;
		} else {
			value=y.getValue_right();
		}
		return value;
	}

	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the biggest value will be returned
	 * @param x value that will be inserted and compared to the values in the node
	 * @param y node that will be compared with the new value to find biggest value
	 * @return biggest value
	 */
	public int findBigValue(int x, Node y){
		int value=0;
		if(x>y.getValue_right()){
			value=x;
		} else {
			value=y.getValue_right();
		}
		return value;
	}
	
	/**
	 * Insert value to the tree. If the x exist : update posting list, if not find the best place and do balancing 
	 * Inserted value will be started from the leaf
	 * @param x value that will be inserted in the tree
	 */
	public void insert (int x){
		Node tujuan = trace(x);
		if(tujuan.getValue_right()==x||tujuan.getValue_left()==x){ //if the x has been existed -> update posting list
			tujuan.updatePostingList(x, 2);
		} else {
			this.jumVal++;
			if(!tujuan.isFull()){					//if the leaf empty, x can be directly insert to the leaf
				tujuan.setValue(x);
			} else {								// the leaf full -> do balancing
				Node masuk = new Node(x);
				balance(tujuan,masuk);
			}
		}
	}
	
	/**
	 * Balance the tree
	 * @param tujuan Existing node
	 * @param masuk new node that will be inserted
	 */
	public void balance(Node parent, Node masuk){
//		System.out.println();
//		System.out.println("yang dimasukin : "+masuk.getValue_left());
		Node gp = new Node(0);												//grand parent -> if there is one value be kicked will be the parent for the others two values
		
		//this looping will stop until : pointer in root or parent that picked not full or stack is empty
		while(!stack.isEmpty()&&parent.isFull()&&parent!=getRoot()){
			gp = new Node(0);												//refresh grand parent
//			System.out.println("parent : "+parent.getValue_left()+","+parent.getValue_right());
//			System.out.println("masuk : "+masuk.getValue_left()+","+masuk.getValue_right());
			if(masuk.getValue_left()<parent.getValue_left()){							//case4 : parent full, new value that will be inserted is the smallest
//				System.out.println("case a");
				gp.setValue_left(parent.getValue_left());
				parent.setValue_left(parent.getValue_right());
				parent.setValue_right(0);
				parent.setNode_left(parent.getNode_middle());
				parent.setNode_middle(parent.getNode_right());
				parent.setNode_right(null);
				gp.setNode_left(masuk);
				gp.setNode_middle(parent);
			} else if(masuk.getValue_left()<parent.getValue_right()){					//case5 : parent full, new value that will be inserted is the middle value
//				System.out.println("case b");
				gp=masuk;
				Node sibling_parent = new Node(parent.getValue_right());
				sibling_parent.setNode_left(gp.getNode_middle());
				sibling_parent.setNode_middle(parent.getNode_right());
				parent.setNode_middle(gp.getNode_left());
				parent.setValue_right(0);
				parent.setNode_right(null);
				gp.setNode_left(parent);
				gp.setNode_middle(sibling_parent);
//				System.out.println("gp : "+gp.getValue_left()+","+gp.getValue_right());
//				System.out.println("anak kiri gp : "+gp.getNode_left().getValue_left()+","+gp.getNode_left().getValue_right());
//				System.out.println("anak kanan gp : "+gp.getNode_middle().getValue_left()+","+gp.getNode_middle().getValue_right());
			} else if(masuk.getValue_left()>parent.getValue_right()){					//case6 : parent full, new value that will be inserted is the biggest
//				System.out.println("case c");
				gp.setValue_left(parent.getValue_right());
				parent.setNode_right(null);
				parent.setValue_right(0);
				gp.setNode_left(parent);
				gp.setNode_middle(masuk);
			}
//			System.out.println("gp : "+gp.getValue_left()+","+gp.getValue_right());
//			System.out.println("anak kiri gp : "+gp.getNode_left().getValue_left()+","+gp.getNode_left().getValue_right());
//			System.out.println("anak tengah gp : "+gp.getNode_middle().getValue_left()+","+gp.getNode_middle().getValue_right());
			parent = stack.pop();
			masuk=gp;
		}
		
//		System.out.println("parent : "+parent.getValue_left()+","+parent.getValue_right());
//		System.out.println("masuk : "+masuk.getValue_left()+","+masuk.getValue_right());
		
		gp = new Node(0);																	//refresh grand parent
		if(parent.getValue_right()==0){														//root empty
			if(masuk.getValue_left()<parent.getValue_left()){								//case2 : parent (root) empty, new value that will be inserted is smaller
//				System.out.println("case e");
				
				parent.setValue_right(parent.getValue_left());
				parent.setNode_right(parent.getNode_middle());
				parent.setValue_left(masuk.getValue_left());
				parent.setNode_left(masuk.getNode_left());
				parent.setNode_middle(masuk.getNode_middle());
				
//				System.out.println("parent : "+parent.getValue_left()+","+parent.getValue_right());
//				System.out.println("masuk : "+masuk.getValue_left()+","+masuk.getValue_right());
				
			}else if(masuk.getValue_left()>parent.getValue_left()){							//case3 : parent (root) empty, new value that will be inserted is bigger
//				System.out.println("case f");
				parent.setValue_right(masuk.getValue_left());
				parent.setNode_middle(masuk.getNode_left());
				parent.setNode_right(masuk.getNode_middle());
			}
		} else {																			//root not empty
			if(masuk.getValue_left()<parent.getValue_left()){								//parent (root) full, new value that will be inserted is the smallest
//				System.out.println("case h");
				gp.setValue_left(parent.getValue_left());
				setRoot(gp);
				parent.setValue_left(parent.getValue_right());
				parent.setValue_right(0);
				parent.setNode_left(parent.getNode_middle());
				parent.setNode_middle(parent.getNode_right());
				parent.setNode_right(null);
				gp.setNode_left(masuk);
				gp.setNode_middle(parent);
			} else if(masuk.getValue_left()<parent.getValue_right()){						//parent (root) full, new value that will be inserted is the middle value															
//				System.out.println("case i");
				gp.setValue_left(parent.getValue_right());
				gp.setNode_left(masuk.getNode_middle());
				gp.setNode_middle(parent.getNode_right());
				parent.setNode_middle(masuk.getNode_left());
				parent.setNode_right(null);
				parent.setValue_right(0);
				setRoot(masuk);
				root.setNode_left(parent);
				root.setNode_middle(gp);
			} else if(masuk.getValue_left()>parent.getValue_right()){						//parent (root) full, new value that will be inserted is the biggest
//				System.out.println("case j");
				gp.setValue_left(parent.getValue_right());
				setRoot(gp);
				parent.setNode_right(null);
				parent.setValue_right(0);
				gp.setNode_left(parent);
				gp.setNode_middle(masuk);
			}
		}
//		System.out.println();
	}
	
	/**
	 * printing the tree and all the value consisted
	 * @param tree that will be printed
	 */
	public void print(Node tree) {
		if (tree != null) {
			System.out.print(tree.getValue_left()+"|");
			System.out.print(tree.getValue_right());
			System.out.print(' ');
			
			print(tree.getNode_left());
					
			print(tree.getNode_middle());
			
			print(tree.getNode_right());
			
		}
	}
	
	/**
	 * saving tree as an object in a file
	 * @param ob name of the object
	 * @param namaFile name of the file
	 */
	public static void save(Object ob, String namaFile){
//		System.out.println("--> Saving object...");
		try{
			FileOutputStream f_out = new FileOutputStream(namaFile);
			ObjectOutputStream obj_out = new ObjectOutputStream(f_out);
			obj_out.writeObject(ob);			
		}catch (Exception e){
			System.out.println(e.toString());
			System.exit(1);
		}
	}
	
	/**
	 * load file that consist tree object
	 * @param namaFile name of the file that will be loaded
	 * @return tree object
	 */
	public static Object load(String namaFile){
		Object ob = new Object();
//		System.out.println("--> Loading saved object...");
		try{
			FileInputStream f_in = new FileInputStream(namaFile);
			ObjectInputStream obj_in = new ObjectInputStream(f_in);
			ob = obj_in.readObject();			
		}catch (Exception e){
			System.out.println(e.toString());
			System.exit(1);
		}
		return ob;
	}
	
	/**
	 *
	public void MakeKamus(){
		try {
			Class.forName("com.mysql.jdbc.Driver");
			Connection connection = DriverManager.getConnection("jdbc:mysql://localhost/finalproject_web?user=root");
			Statement statement = connection.createStatement();
			ResultSet result = statement.executeQuery("select kata from token");
			ScapegoatTree tree = new ScapegoatTree();
			while(result.next()){
				tree.insert(result.getString("kata").hashCode());
			}
			
			Helper.save(tree, "kamus_bahasa_indonesia.sgt");
		} catch (SQLException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	*/
	
}